Date: Wed, 20 Nov 1996 22:16:42 GMT
Server: NCSA/1.5.1
Last-modified: Sun, 10 Nov 1996 02:23:33 GMT
Content-type: text/html
Content-length: 9813

<head>
<TITLE>CPS 149S, Fall 1996 </TITLE>
<LINK REV="made" HREF="mailto:ola@cs.duke.edu">
</head>
<body bgcolor="#FFFFFF">

<center>

<HR>
<TABLE BORDER=0 CELLSPACING=2>
<TR>
<TD align=center>
<!WA0><A href="http://www.cs.duke.edu/~ola">
<!WA1><IMG ALIGN=center SRC="http://www.cs.duke.edu/~ola/images/olasmall.gif" ALT="*">
</TD>
</A>
<TD ALIGN=center>
<H1>
CPS 149S: Problem Solving Seminar
</H1>
</TD>
<TD align=center>
<!WA2><A href="http://www.cs.duke.edu/~rodger">
<!WA3><IMG ALIGN=center SRC="http://www.cs.duke.edu/~ola/images/rodger.gif"></TD>
</A>
</TR>
<TR>
<TD COLSPAN=3 ALIGN=center>
<H3>
Problem Solving Seminar: Programming Contest Practice
</H3>
</TD>
</TR>

</TABLE>

</center>

<p>
<CENTER>
[ 
<!WA4><A href="#overview"> Overview </A> |
<!WA5><A href="#syllabus"> Syllabus </A> |
<!WA6><A href="#assign"> Assignments </A> |
<!WA7><A href="#grades"> Grades </A> |
<!WA8><A href="#people"> People </A> |
<!WA9><A href="#code"> Code </A>]
</CENTER>

<hr>

<DL>
<DT>
<!WA10><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> 
<strong> Professors  </strong><BR>

<TABLE>
<TR VALIGN=TOP>
<TD>
<!WA11><A href="http://www.cs.duke.edu/~ola"> Owen Astrachan</A>
<DD> 
<UL>
<li> Office: D241, LSRC
<li> email: <!WA12><A href="mailto:ola@cs.duke.edu"> ola@cs.duke.edu
</A> or <!WA13><A href="mailto:ola@acpub.duke.edu"> ola@acpub.duke.edu
</A>
<li> phone: 660-6522
<li> office hours: Monday 2:00-3:30, Thursday 11:00-12:30 <br>
any time for quick questions
</UL>
</TD>
<TD>
<!WA14><A href="http://www.cs.duke.edu/~rodger"> Susan Rodger</A>
<DD> 
<UL>
<li> Office: D237, LSRC
<li> email: <!WA15><A href="mailto:rodger@cs.duke.edu"> rodger@cs.duke.edu
</A> or <!WA16><A href="mailto:rodger@acpub.duke.edu"> rodger@acpub.duke.edu
</A>
<li> phone: 660-6595
<li> Mon 5:15-6:16 pm, Tue 1-2 pm, Fri 1:30-2:30 pm
</UL>
</TD>
</TR>
</TABLE>

<p>

</DL>

<hr>

<H2> <A NAME="overview"> Course Overview </A> </H2>

<EM>From the Course Catalog</EM> 
<P>
Techniques for attacking, solving, and writing computer programs for
challenging computational problems.  Algorithmic and Programming
Language toolkits.
<P>
<EM>What the course is about</EM>
<P>
The course is intended to provide practice for participation in the ACM
programming contest.  The regional contest will be held on November
16th at several sites, this year Duke is a site.  
People in CPS 149S are expected to participate in the
contest.  The top two teams in the region go to the world finals.
This year's finals will be held in San Jose, CA
on March 2, 1997.  

<HR>
<H2> <A NAME="syllabus"> Syllabus </A> </H2>
 <P> 

Each week three problems will be assigned.  We anticipate ten weeks
of problems (with some time off for fall break and for the regional
contest).  Thus a total of 30 problems will be assigned.  We will try to
make one of the problems each week a challenge.  The other two problems
will be easier, but still require an effort to get completely correct.
<P>

<HR>
<H2> <A NAME="grading"> Grading </A> </H2>
<P> 
Coded solutions will be graded on a scale of 0, 2, 6, 10.  A 10 point
solution solves all input test files correctly.  A 6 point solution
solves some test files, but not all.  A 2 point solution represents an
honest effort at an attempt, but may not solve the problem for any
test data.  An honest effort is subject to interpretation, but we
anticipate that it represents at least two hours of work.
 <P>
Problems done individually earn full credit.  For group solutions, the
points earned are split among the group members so that a perfect
solution for a two-person group earns each person 5 points.  
 <P>
Two cut-offs have been established: 120 points earns an A, 80 points
earns a B.  We might lower these cutoffs but we will not raise them.
Each student must also make one presentation of a solution.  Failure to
present a solution will cause a 10 point deduction in total points.
 <P>
Students participating in the regional contest can earn points for
problems solved in the contest.  We may give full credit for all
problems solved to each team member
rather than dividing credit among team members.


<hr>
<h2> <A NAME="assign">Assignments</A> </h2>

Each assignment should include a <EM>README</EM> file with the names of all group
members (or just one name if an individual attempt) and the time it took to
complete.  Turn in only one program for each group attempt.

<DL>
<DT>
<!WA17><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> First week
<DD> 
<UL>
<LI> <!WA18><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week1/html.html">html parsing</A>
Turn this in using <TT>submit149 html README ...</TT>
<LI> <!WA19><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week1/samegame.html">quasi-tetris</A>
Turn this in using <TT>submit149 tetris README ...</TT>
<LI> <!WA20><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week1/nonstop.html">stop 'n go</A>
Turn this in using <TT>submit149 stopgo README ...</TT>
</UL>
<P>

<DT>
<!WA21><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Second week
<DD> 
<UL>
<LI> <!WA22><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week2/solitaire.html">solitaire simulation</A>
Turn this in using <TT>submit149 solitaire README ...</TT>
<LI> <!WA23><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week2/pattern.html">pattern matching</A>
Turn this in using <TT>submit149 pattern README ...</TT>
<LI> <!WA24><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week2/trellis.html">trellis automata</A>
Turn this in using <TT>submit149 trellis README ...</TT>
</UL>
 <P>

<DT>
<!WA25><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Third week
<DD> 
<UL>
<LI> <!WA26><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week3/intersect.html">intersecting figures</A>
Turn this in using <TT>submit149 intersect README ...</TT>
<LI> <!WA27><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week3/ebnf.html">programming with EB and NF</A>
Turn this in using <TT>submit149 ebnf README ...</TT>
<LI> <!WA28><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week3/color.html">graph color</A>
Turn this in using <TT>submit149 color README ...</TT>
</UL>
 <P>

<DT>
<!WA29><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Fourth week
<DD> 
<!WA30><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week4.html">All problems in one document</A>!
<UL>
<LI> Wormhole, turn in using <TT>submit149 wormhole README ...</TT>
<LI> Differentiation, turn in using <TT>submit149 differ README ..</TT>
<LI> Finding moles, turn in using <TT>submit149 mole README ..</TT>
</UL>
 <P>
<DT>
<!WA31><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Fifth week
<DD> 
<!WA32><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week5.html">All problems in one document</A>!
<UL>
<LI> Holes in buckets, turn in using <TT>submit149 buckets README ...</TT>
<LI> Chromatic coloring, turn in using <TT>submit149 chromatic 
README ..</TT>
<LI> Data compression, turn in using <TT>submit149 compress README ..</TT>
</UL>
 <P>
<DT>
<!WA33><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Sixth week
<DD> 
<UL>
<LI> <!WA34><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week6/crows.html">Counting Crows</A>
Turn this in using <TT>submit149 birdy README ...</TT>
 <P>
<LI> <!WA35><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week6/wordy.ps">Lexicographical Ordering
(postscript only)</A> 
Turn this in using <TT>submit149 wordy README ...</TT>
</UL>

<DT>
<!WA36><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Seventh Week, practice contest
<DD> 
<UL>

<LI> <!WA37><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/contest/p1.html">hailstone numbers</A>
submit with <TT>submit149 hailstone</TT>
<LI> <!WA38><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/contest/p2.html">perimeter</A>
submit with <TT>submit149 perimeter</TT>
<LI> <!WA39><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/contest/p3.html">morse code</A>
submit with <TT>submit149 morse</TT>
<LI> <!WA40><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/contest/p4.html">crazy eights</A>
submit with <TT>submit149 crazy</TT>
</UL>

<DT>
<!WA41><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Eighth Week
<DD> 
<!WA42><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week8.ps">Problems from East Central Contest of
1996 (postscript only)</A>
<UL>
<LI> Problem 1: Submit using submit149 <STRONG>meetmatch</STRONG>
<LI> Problem 2: Submit using submit149 <STRONG>superselect</STRONG>
<LI> Problem 3: Submit using submit149 <STRONG>polypuzzle</STRONG>
<LI> Problem 4: Submit using submit149 <STRONG>wordsearch</STRONG>
<LI> Problem 5: Submit using submit149 <STRONG>mpi</STRONG>
<LI> Problem 6: Submit using submit149 <STRONG>bigint</STRONG>
<LI> Problem 7: Submit using submit149 <STRONG>encrypt</STRONG>

</UL>

<DT>
<!WA43><IMG SRC=http://www.cs.duke.edu/images/redball.gif ALT="*"> Ninth Week
<DD> 
Problems from the Southeast regionals.  Postscript only.
 <P>
<!WA44><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/errata.html"><STRONG>Errata</STRONG></A>
 <P>
<UL>
<LI>  <!WA45><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/cutting.ps">Problem 1</A>
submit using <STRONG>cutting</STRONG>

<LI>  <!WA46><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/divide.ps">Problem 2</A>
submit using <STRONG>divide</STRONG>

<LI>  <!WA47><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/factor.ps">Problem 3</A>
submit using <STRONG>factor</STRONG>

<LI>  <!WA48><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/hives.ps">Problem 4</A>
submit using <STRONG>hives</STRONG>

<LI>  <!WA49><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/mismatch.ps">Problem 5</A>
submit using <STRONG>mismatch</STRONG>

<LI>  <!WA50><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/robbers.ps">Problem 6</A>
submit using <STRONG>robbers</STRONG>

<LI>  <!WA51><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/seconds.ps">Problem 7</A>
submit using <STRONG>seconds</STRONG>

<LI>  <!WA52><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/title.ps">Problem 8</A>
submit using <STRONG>title</STRONG>

<LI>  <!WA53><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/webpage.ps">Problem 9</A>
submit using <STRONG>webpage</STRONG>

<LI>  <!WA54><A HREF="http://www.cs.duke.edu/~ola/courses/cps149/problems/week9/welfare.ps">Problem 10</A>
submit using <STRONG>welfare</STRONG>

</UL>


</DL>

<hr>
<h2> <A NAME="grades">Grades</A> </h2>


<hr>
<h2> <A NAME="people">People</A> </h2>

Here's a list of people enrolled in the class

<UL>
<LI> Gretta Bartels
<LI> Sarah Christopher
<LI> Eric Gramond
<LI> Michael Hoeffner
<LI> Eric Jewart
<LI> Jay Kamm
<LI> Ken Leider
<LI> Neill Occhiogrosso
<LI> Rachel Pottinger
<LI> Travis Pouarz
<LI> Robert Schneck
<LI> Noam Shazeer
<LI> Craig Silverstein
<LI> Adrian Sisser
<LI> Steve Wolfman
<LI> David Woodward
<LI> Jon Wray
</UL>
 <P>
Here's a list of people who attend often and submit code

<UL>
<LI> 
</UL>



<hr>
<h2> <A NAME="code">Code</A> </h2>
Some code examples discussed in class.


<hr>
<address>
Last modified September 2, 1996 by Owen Astrachan, ola@cs.duke.edu
</address>
</body>

